//题目:
// 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
// 数字 1-9 在每一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
#include<iostream>
#include<queue>
#include<unordered_map>
#include<limits.h>
#include<algorithm>

using namespace std;
//代码:
class Solution {
public:
    struct compare_row
    {
        bool operator()(const pair<int,int>& pir1,const pair<int,int>& pir2)
        {
            return pir1.first<pir2.first;
        }
    };
    struct compare_col
    {
        bool operator()(const pair<int,int>& pir1,const pair<int,int>& pir2)
        {
            return pir1.second<pir2.second;
        }
    };
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<char,vector<pair<int,int>>> mp;
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)  
            {
                if(board[i][j]!='.')mp[board[i][j]].push_back({i,j});
            }
        }
        //得到某一个字符出现的所有位置，下面对这些位置做判断即可
        for(auto& _mp:mp)
        {
            vector<pair<int,int>> v(_mp.second);
            //判断是否在同一行
            sort(v.begin(),v.end(),compare_row());
            for(int i=0;i<v.size()-1;i++)
                if(v[i].first==v[i+1].first)return false;
            //判断是否在同一列
            sort(v.begin(),v.end(),compare_col());
            for(int i=0;i<v.size()-1;i++)
                if(v[i].second==v[i+1].second)return false;
            //判断九宫格
            for(int i=0;i<9;i+=3)
            {
                for(int j=0;j<9;j+=3)
                {
                    int count=0;
                    for(int k=0;k<v.size();k++)
                    {
                        //左上角(i,j) 右下角(i+3,j+3)
                        if(v[k].first>=i && v[k].second>=j && v[k].first<i+3 && v[k].second<j+3)
                            count++;
                        if(count==2)
                            return false;
                    }
                }
            }
        }
        return true;
    }
};